package com.hy;

import java.util.Arrays;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 插入排序
 * author: Mr.Du
 * Date: 2022/11/12
 * Time: 9:58
 */
public class InsertSort {
    
    public static void main(String[] args) {
        InsertSort iSort = new InsertSort();
        int[] nums = new int[10];
        Random r = new Random();
        // 跑五次
        for(int i = 0;i < 5;i++){
            for(int j = 0; j < nums.length;j++){
                nums[j] = r.nextInt(1000);
            }
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(nums));
            iSort.insertSort(nums);
            System.out.println("插入排序后的数组: ");
            System.out.println(Arrays.toString(nums));
        }
    }
    
    /**
     * 排序思想：
     * 1.从第一个元素开始，我们认为第一个元素已经被排序
     * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置
     * 5.执行第二步骤，直到所有元素遍历完
     *
     * @param nums
     */
    public void insertSort(int[] nums){
        for(int i = 1;i < nums.length;i++){
            int tmp = nums[i];
            int j = i - 1;
            while(j >=0 && nums[j] > tmp){
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = tmp;
            
        }
    }
}
